// 解题思路：
// 题目要求：从数组中找最大和，使得能够被 3 整除
// 正难则反的解题思路：可以求所有数的和 ret，如果 ret 能够被 3 整除，返回 ret
// 如果模 3 余 1，找一个最小的能够模 3 余 1 的最小值或者两个能够模 3 余 2 的最小值
// 同理，如果模 3 余 2，找一个最小的能够模 3 余 2 的最小值或者两个能够模 3 余 1 的最小值
// 使用贪心的方法：
// 找到数组中最小的两个数 a1 和 a2，能够模 3 余 1
// 找到数组中最小的两个数 b1 和 b2，能够模 3 余 2
// 如果模 3 余 1，返回 max(ret - a1, ret - b1 - b2)
// 如果模 3 余 2，返回 max(ret - b1, ret - a1 - a2)

// 动态规划的解法：
// dp[i][j] 表示以 i 位置为结尾的余数为 j 的最大和
// 数组多开一行
// 初始化：dp[0][0] = 0, dp[0][1] = Integer.MIN_VALUE, dp[0][2] = Integer.MIN_VALUE
// 状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][3 + j - nums[i - 1] % 3] + nums[i - 1])

public class Solution {
    public int maxSumDivThree1(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for(int x : nums) ret += x;

        if(ret % 3 == 0) return ret;

        int a1 = 50000, a2 = 50000, b1 = 50000, b2 = 50000;

        for(int x : nums){
            if(x % 3 == 1){
                if(x < a1){
                    a2 = a1;
                    a1 = x;
                } else if(x < a2){
                    a2 = x;
                }
            } else if(x % 3 == 2) {
                if(x < b1) {
                    b2 = b1;
                    b1 = x;
                } else if(x < b2) {
                    b2 = x;
                }
            }
        }
        int t = ret % 3;
        if(t == 1) return Math.max(ret - a1, ret - b1 - b2);
        else return Math.max(ret - a1 - a2, ret - b1);
    }

    public int maxSumDivThree2(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 1][3];

        dp[0][0] = 0;
        dp[0][1] = -50000;
        dp[0][2] = -50000;

        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 3; j++){
                dp[i][j] = dp[i - 1][j];
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][(3 + j - nums[i - 1] % 3) % 3] + nums[i - 1]);
            }
        }

        return dp[n][0];
    }
}
